package prac6;

public class FasterLinkedSet <T extends Comparable<T>> extends LinkedSet<T> {
	/**
	 * @complexity	Best and worst case: O(1)
	 */
	public FasterLinkedSet (){
		theSet = new SortedLinkedList<T>();
	}
	
	/**
     * Add a new item to this list.
     * 
     * @param       newItem to add to this list
	 * @complexity	Best case: O(M) - item is already contained in the set as the first member
	 * 				Worst case: O(M*N) - item is not already contained in the set
	 * 				where	M is the complexity of comparing item and a member of the set
	 * 						N is the number of items in the set.
     * @post        the item will appear in the list. Where? it will depend on
     *              the particular concrete class
     */
	public void add(T newItem){
		if(!theSet.find(newItem)){
			theSet.add(newItem);
		}

	}
	
	/**
	 * Finds the intersection of this set and otherSet
	 * 
	 * @param		otherSet the set we're finding the intersection of this set with
	 * @return		The intersection set
	 * @complexity	Best case: O(M) - The sets are the same
	 * 				Worst case: O(M + N1*C) - The sets are completely different
	 * 				where	N1 is the size of this set
	 * 						N2 is the size of the other set
	 * 						C is the complexity of comparing two elements of the sets
	 */
	public FasterLinkedSet<T> intersection(FasterLinkedSet<T> otherSet) {
		if (theSet.equals(otherSet)){
			return otherSet;
		} else {
			FasterLinkedSet<T> intersectionSet = new FasterLinkedSet<T>();
			Iterator<T> i = theSet.iterator();
			Iterator<T> j = otherSet.iterator();
			while (i.hasNext()){
				if(i.peek().compareTo(j.peek()) == 0){
					intersectionSet.add(i.peek());
					i.next();
					j.next();
				}
				else if(i.peek().compareTo(j.peek()) == 1){
					j.next();
				}
				else {
					i.next();
				}
			}
			return intersectionSet;
		}
	}

}
